package com.leetcode.partition5;


import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/9/24 8:30
 */
public class LC430扁平化多级双向链表 {

    public static Node flatten(Node head) {
        if (head == null) return head;
        List<Integer> path = new ArrayList<>();
        dfs(head, path);
        Node newHead = new Node(), prev = newHead;
        for (Integer item : path) {
            Node newNode = new Node();
            newNode.val = item;
            newNode.prev = prev;
            prev.next = newNode;

            prev = newNode;
        }
        Node ans = newHead.next;
        ans.prev = null;
        return ans;
    }

    public static void main(String[] args) {
        Node l1 = new Node(1);
        Node l2 = new Node(2);
        Node l3 = new Node(3);
        Node l4 = new Node(4);
        Node l5 = new Node(5);
        Node l6 = new Node(6);
        Node l7 = new Node(7);
        Node l8 = new Node(8);
        Node l9 = new Node(9);
        Node l10 = new Node(10);
        Node l11 = new Node(11);
        Node l12 = new Node(12);
        l1.next = l2;
        l2.next = l3;
        l2.prev = l1;
        l3.next = l4;
        l3.prev = l2;
        l4.next = l5;
        l4.prev = l3;
        l5.next = l6;
        l5.prev = l4;
        l6.prev = l5;

        l7.next = l8;
        l8.next = l9;
        l8.prev = l7;
        l9.next = l10;
        l9.prev = l8;
        l10.prev = l9;

        l11.next = l12;
        l12.prev = l11;

        l3.child = l7;
        l8.child = l11;
        Node res = flatten(l1);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }

    private static void dfs(Node cur, List<Integer> path) {
        if (cur == null) return;
        path.add(cur.val);
        dfs(cur.child, path);
        dfs(cur.next, path);
    }

    private static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;

        public Node() {
        }

        public Node(int val) {
            this.val = val;
        }
    }
}
